package com.leetcode.problems023;


import com.leetcode.util.ListNode;

import java.util.List;

/**
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }

        if(lists.length == 1){
            return lists[0];
        }

        ListNode dummyNode = new ListNode(0);

        ListNode cur = dummyNode;
        while (true){
            int minIndex = 0;
            ListNode minNode = lists[0];
            for (int i = 0; i < lists.length; i++) {
                if(lists[i] != null && (minNode == null || minNode.val > lists[i].val)){
                    minNode = lists[i];
                    minIndex = i;
                }
            }
            if(minNode == null){
                break;
            }
            cur.next = minNode;
            cur = cur.next;
            lists[minIndex] = lists[minIndex].next;
        }
        return dummyNode.next;
    }
    public static void main(String[] args) {
        int[] arr = {1,4,5};
        int[] arr1 = {1,3,4};
        //int[] arr2 = {2,6};
        ListNode[] re = new ListNode[]{ListNode.getListFormArray(arr),ListNode.getListFormArray(arr1)};
        ListNode.printListNode(new Solution().mergeKLists(re));
    }
}
